package com.tgy.algorithm.base._滑动窗口;

import java.util.Arrays;
import java.util.LinkedList;

public class _每次滑动窗口的最大值_01 {

    public static int[] getWindowMax(int[] nums, int win) {

        int len = nums.length;
        if (nums == null || len == 0 || win <= 0) {
            return null;
        }

        if (win > len) {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                max = Math.max(max,nums[i]);
            }

            return new int[]{max};
        }

        int[] res = new int[len - win + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        int value;
        for (int i = 0; i < len; i++) {
            value = nums[i];
            while (!queue.isEmpty() && nums[queue.peekLast()] <= value) {
                queue.pollLast();
            }
            queue.offerLast(i);

            int leftW = i - win;
            if (queue.peekFirst() == leftW) {
                queue.pollFirst();
            }

            if (leftW+1 >= 0) {
                res[leftW+1] = nums[queue.peekFirst()];
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {4,3,5,4,3,3,6,7};
        int[] windowMax = getWindowMax(nums, 100);
        System.out.println(Arrays.toString(windowMax));
    }
}
